package 动态规划.斐波那契数列;

import java.util.Arrays;

public class 打家劫舍II_213 {
    public static void main(String[] args) {
        int rob = new 打家劫舍II_213().rob(new int[]{2, 3, 2});
        System.out.println(rob);
    }

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] case1 = Arrays.copyOfRange(nums, 0, nums.length - 1);//不偷最后一家
        int[] case2 = Arrays.copyOfRange(nums, 1, nums.length);//不偷第一家

        return Math.max(help(case1), help(case2));

    }

    //像小偷第一版【198题】一样，求出可以抢到的最多的财富，注意并不是环，只是普通数组
    public int help(int[] nums) {

        int N = nums.length;
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= N; i++) {
            //198题的状态转移方程
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }

        return dp[N];
    }
}
